module map2D {
	/*
	 * A* 寻路算法
	 * 
	 * @author Dingo
	 * @version 1.0
	 * @date 070831
	 */
	export class AStar implements GYLite.IListener{
		public testLay:GYLite.GYSprite;

		/**是否允许寻路时斜线走动*/public canDiaonal:boolean;
		//垂直或水平移动一格的代价
		private COST_STRAIGHT:number = 10;
		//斜向移动一格的代价
		private COST_DIAGONAL:number = 14;
		//逆向偏离目标的代价
		private COST_INSERVE:number = 80;
		//起始节点ANode
		private _ndStart:ANode;
		//目标节点ANode
		private _ndEnd:ANode;
		//当前节点ANode
		private _ndCurrent:ANode;
		//最大寻路步数限制
		private _nMaxTry:number;
		//尝试次数计数器
		private _nCrtTry:number;
		//开放表，元素为ANode类型
		private _aOpenList:ANode[];
		//关闭表，元素为ANode类型
		private _aCloseList:ANode[];
		//尝试表，元素为ANode类型
		private _aTryList:ANode[];
		//八个方向数组，从节点正上方开始，顺时针排列
		private static aDir:any[] = [[0,-1],[1,-1],[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1]];
		//地图节点数组
		// public aNodeMap:number[] = [];
		//地图宽度(格子列数)
		private _mapWidth:number;
		//地图宽度(格子行数)
		private _mapHeight:number;
		//记录节点在aOpenList数组的位置
		// private _num:number;
		//路径数组
		// public aPath:any[];
		//是否找到路径
		// public bPathFind:boolean;
		//场景对象
		private _scene:IScene;
		private _listenId:number =-1;
		private _debug:boolean;
		//构造函数
		public constructor(scene:IScene,debug:boolean = false) {
			let s = this;
			s._nMaxTry = 600;
			s._nCrtTry = 0;
			s._aOpenList = [];
			s._aCloseList = [];			
			s._mapWidth = scene.mapGridCol;//amap[0].length;
			s._mapHeight = scene.mapGridRow;//amap.length;
			s._scene = scene;
			s.canDiaonal = true;
			s._aTryList = [];	
			s._debug = debug;		
			// s.aNodeMap = amap;
		}		
		//添加到open表
		// public addFirstOpen():void{
		// 	let s = this;
		// 	s.aOpenList.push(s.ndStart);
		// }
		//取得指定点周围可通过的点，从正上方开始
		private getRound(apos:number[]):number[][]{
			let s = this;
			var arr:number[][] = [];			
			for(var i:number=0;i<AStar.aDir.length;i++){
				var xp = apos[0] + AStar.aDir[i][0];
				var yp = apos[1] + AStar.aDir[i][1];
				if(s.isStart([xp,yp]) || !s.isPass([xp,yp]) || s.isCorner([xp,yp]) || s.isInClose([xp,yp]))
					continue
				arr.push([xp,yp]);				
			}			
			return arr;
		}		
		// //是否超出地图范围
		// private isOutRange(apos:any[]):boolean{
		// 	let s = this;
		// 	if(apos[0]<0 || apos[0] >= s.mapwidth || apos[1] < 0 || apos[1]>= s.mapheight)
		// 		return true;
		// 	return false;
		// }		
		//是否是起点
		private isStart(apos:number[]):boolean{ 
			let s =this;
    		if(apos[0] == s._ndStart.pos[0] && apos[1] == s._ndStart.pos[1])
       			return true;
    		return false;
		}
		// //是否可以通过		
		private isPass(apos:number[]):boolean{ 
			let s = this;
			// if(s.isOutRange(apos)){
			// 	return false;
			// }else{	
			// 	return (s.aNodeMap[apos[1]][apos[0]]>0?false:true);
			// }
			return s._scene.canGridPass(apos[0],apos[1]) > 0;
		}				
		//是否不可通行的拐角
		private isCorner(apos:number[]):boolean{
			let s = this;			
			if(s.isPass(apos)){
				if(apos[0] > s._ndCurrent.pos[0]){
					if(apos[1] > s._ndCurrent.pos[1]){
						if(!s.canDiaonal)return true;
						if(!s.isPass([apos[0] - 1,apos[1]]) || !s.isPass([apos[0],apos[1] - 1]))
							return true;
					}
					else if(apos[1] < s._ndCurrent.pos[1]){
						if(!s.canDiaonal)return true;
						if(!s.isPass([apos[0] - 1,apos[1]]) || !s.isPass([apos[0],apos[1] + 1]))
							return true;
					}
				}
				else if(apos[0] < s._ndCurrent.pos[0]){
					if(apos[1] > s._ndCurrent.pos[1]){
						if(!s.canDiaonal)return true;
						if(!s.isPass([apos[0] + 1,apos[1]]) || !s.isPass([apos[0],apos[1] - 1]))
							return true;
					}
					else if(apos[1] < s._ndCurrent.pos[1]){
						if(!s.canDiaonal)return true;
						if(!s.isPass([apos[0] + 1,apos[1]]) || !s.isPass([apos[0],apos[1] + 1]))
							return true;
					}
				}
			}
			return false;
		}
		//是否在开启列表中
		//获得传入参数在aOpenlist数组的位置，如不存在返回false，存在为true，位置索引保存到变量num中。
		private isInOpen(apos:number[]):number{
			let s = this;
    		// var bool:boolean = false;
			var id = apos[1] * s._mapWidth + apos[0];
    		for(var i=0;i<s._aOpenList.length;i++){
        		if(s._aOpenList[i].id == id){
          			// bool = true;
					// s._num = i;
					return i;
					// break;
				}
   			}
    		// return bool;
			return -1;
		}
		//是否在关闭列表中
		private isInClose(apos:any[]):boolean{
			let s =this;
			var bool:boolean = false;
			var id = apos[1] * s._mapWidth + apos[0];
    		for(var i=0;i<s._aCloseList.length;i++){
        		if(s._aCloseList[i].id == id){
            		bool=true;
					break;
				}
    		}
    		return bool;
		}
		//取得F值，参数为某一节点周围的节点
		private getF(around:number[][]):void{ 
		    //f,综合的距离值；
			//h,给定节点到目标点的距离值；
			//g,起点到给定节点的距离值
			let f:number,g:number,h:number;
			let s =this;			
			let apos:number[];
			for(var i:number = 0;i < around.length;i++){					
				apos = around[i];					
				//是否与起点在同一直线上
				if(apos[0] == s._ndStart.pos[0] || apos[1] == s._ndStart.pos[1]){
					g = s._ndCurrent.G + s.COST_STRAIGHT;
				}else{
					g = s._ndCurrent.G + s.COST_DIAGONAL;
				}
				//如果当前点已存在aOpenlist数组中
				let ind:number = s.isInOpen(apos);
				if(ind > -1){
					var opos:ANode = s._aOpenList[ind];
					//如果当前点G值更小，更改父节点
					if(g<opos.G){
						opos.F = g + opos.H;
						opos.G = g;
						opos.pid = s._ndCurrent.id;
					}else{
						g = opos.G;
					}
				}
				//否则将当前点添加到aOpenList数组
				else{
					h = s.calculateH(s._ndCurrent.pos,apos,s._ndEnd.pos);//(Math.abs(s._ndEnd.pos[0] - apos[0]) + Math.abs(s._ndEnd.pos[1] - apos[1])) * s.COST_STRAIGHT;//估值
					f= g + h;
					var newnode:ANode = ANode.createANode(apos,apos[1] * s._mapWidth + apos[0],0,s._ndCurrent.id);//new ANode(apos,apos[1] * s.mapWidth + apos[0],0,s.ndCurrent.id);
					newnode.F = f;
					newnode.G = g;
					newnode.H = h;
					s._aOpenList.push(newnode);
				}			
			}
		}
		//估值
		private calculateH(curPos:number[],nextPos:number[],endPos:number[]):number		
		{
			let s = this;
			let dx:number,dy:number,costAdd:number=0;
			dx = endPos[0] - nextPos[0];			
			dy = endPos[1] - nextPos[1];			
			if(curPos[0] < endPos[0] && nextPos[0] < curPos[0])
			{
				costAdd += s.COST_INSERVE * (endPos[0] - curPos[0]);
			}
			else if(curPos[0] > endPos[0] && nextPos[0] > curPos[0])
			{
				costAdd += s.COST_INSERVE * (curPos[0] - endPos[0]);
			}
			if(curPos[1] < endPos[1] && nextPos[1] < curPos[1])
			{
				costAdd += s.COST_INSERVE * (endPos[1] - curPos[1]);
			}
			else if(curPos[1] > endPos[1] && nextPos[1] > curPos[1])
			{
				costAdd += s.COST_INSERVE * (curPos[1] - endPos[1]);
			}
			if(dx < 0)dx  = -dx;
			if(dy < 0)dy  = -dy;
			return (dx + dy) * s.COST_STRAIGHT + costAdd;//(Math.abs(endPos[0] - nextPos[0]) + Math.abs(endPos[1] - nextPos[1])) * s.COST_STRAIGHT
		}
		private sortF(a:any,b:any):number
		{
			return a.F > b.F?-1:1;
		}
		/**搜索路径
		 * @param col 列索引
		 * @param row 行索引
		 * @param trackArr 寻路返回的结果数组，不传则创建一个新数组
		 * @return 如果寻路成功，返回number[][] [[索引x，索引y]……]，失败返回null
		 * */		
		public doSearch(startCol:number,startRow:number,endCol:number,endRow:number,trackArr:number[][]=null):number[][]{
			let s = this;
			let apath:number[][];	
			let t:number;		
			apath = trackArr;
			if(s._debug)			
				t = Date.now();			
			s.clearANodes();
			// s.addFirstOpen();
			s._aTryList.length = 0;
			s._ndCurrent = s._ndStart = ANode.createANode([startCol,startRow],startCol + startRow*s._mapWidth);
			s._ndEnd = ANode.createANode([endCol,endRow],endCol + endRow*s._mapWidth);
			s._aOpenList.push(s._ndStart.clone());
			while(s._aOpenList.length){
				s._nCrtTry ++ ;
				//如果超出寻路步数限制
				if(s._nCrtTry > s._nMaxTry){
					s.destroyData();
					return apath;			
				}
				s._aTryList.push(s._ndCurrent);
				s.getF(s.getRound(s._ndCurrent.pos));
				//按照F值由大到小的顺序排列开启列表
				s._aOpenList.sort(s.sortF);
				//将开启列表最后一位元素列入关闭列表
				var lastNode:ANode = s._aOpenList[s._aOpenList.length - 1];
				s._aCloseList.push(lastNode);				
				s._ndCurrent = lastNode;
				if(s._aOpenList.length>1)
					s._aOpenList.pop();
				//如果当前节点是目标节点，路径找到，返回true
				if(s._ndCurrent.id == s._ndEnd.id){					
					apath = s.getPath(apath);
					s.destroyData();
					// s.bPathFind = true;
					s._ndStart = s._ndCurrent;					
					apath = apath.length > 0?apath:null;
					break;
				}
			}
			// s.bPathFind = false;
			s.destroyData();
			// s.aPath = [];
			if(s._debug)
			{
				console.log("本次寻路耗时："+(Date.now() - t),"步数："+s._aTryList.length);
				s.drawTestPath(apath,s._aTryList);
			}			
			return apath;
		}
		public get tryList():ANode[]
		{
			return this._aTryList;
		}
		//清空各数组
		private destroyData():void{
			let s =this;
			s.clearANodes();
			s._nCrtTry = 0;			
		}
		/**取得路径数组
		 * @param trackArr 寻路返回的结果数组
		*/
		private getPath(trackArr:number[][]):number[][]{
			let s =this;
			var apath:number[][] = trackArr?trackArr:[];
    		var tmpnode:ANode = s._aCloseList[s._aCloseList.length-1];
			apath.push(tmpnode.pos);
			var inc:number = 0;
			while(inc <= s._aCloseList.length){
				inc++
				for(var i:number = 0;i<s._aCloseList.length;i++){
					if(s._aCloseList[i].id == tmpnode.pid){
						tmpnode = s._aCloseList[i];
						apath.push(tmpnode.pos)
					}
					if(tmpnode.id == s._ndStart.id)
						break;
				}
			}
			apath.pop();
			return apath;
		}
		public dataChange(listenId: number): void
		{
			let s = this;
			if(s._listenId == listenId)
			{
				if(s.testLay)
				{
					s.testLay.x = -s._scene.mapX;
					s.testLay.y = -s._scene.mapY;
				}
			}
		}
		public drawTestPath(arr:number[][],tryList:ANode[]):void
		{
			let i:number,len:number;
			let g:egret.Graphics;
			let s =this;
			let gridSize:number;
			if(!s._debug)return;
			if(s.testLay == null)
			{
				s.testLay = new GYLite.GYSprite;
				s.testLay.mouseThrough = true;
				s._scene.sceneLayer.addElement(s.testLay);
				s._listenId = s._scene.mapMoveListener.addListener(s)
			}
			gridSize = s._scene.gridSize;
			g = s.testLay.graphics;
			g.clear();
			if(arr && arr.length > 0)
			{
				len = arr.length;
				for(i=0;i<len;++i)
				{
					g.beginFill(0xff0000,0.5);
					g.drawRect(arr[i][0]*gridSize + 1,arr[i][1]*gridSize + 1,gridSize - 2,gridSize - 2);
				}
				g.endFill();
			}
			if(tryList && tryList.length > 0)		
			{
				len = tryList.length;
				for(i=0;i<len;++i)
				{
					g.beginFill(0x0000ff,0.3);
					g.drawRect(tryList[i].pos[0]*gridSize + 4,tryList[i].pos[1]*gridSize + 4,gridSize - 8,gridSize - 8);
				}
				g.endFill();
			}
		}
		private clearANodes():void
		{
			let s =this;
			let len:number;
			if(s._ndStart)
			{
				s._ndStart.clear();
				s._ndStart = null;
			}
			if(s._ndStart)
			{
				s._ndEnd.clear();
				s._ndEnd = null;
			}			
			len = s._aOpenList.length;
			while(--len > -1)
			{
				s._aOpenList[len].clear();
			}
			len = s._aCloseList.length;
			while(--len > -1)
			{
				s._aCloseList[len].clear();
			}
			s._aOpenList.length = 0;
			s._aCloseList.length = 0;			
		}
		public dispose():void
		{
			let s = this;
			if(s.testLay)
				s.testLay.dispose();
			if(s._listenId > -1)
				s._scene.mapMoveListener.removeListener(s);
			s.clearANodes();
			s._aTryList.length = 0;
		}
	}
}